#include <stdio.h>
#include <stdlib.h>
 typedef struct Index
    {

        int index;
        int val;
    } Index;



/**
 *
 * 此解法较为快速
 *
 * 思路也特别简单，就是先把最高的长度相乘作为面积。
 * 然后减去这些柱子占用的面积
 * 然后减去左右两把不能节水的面积
 *
 */
int trapquik(int* height, int heightSize){


    int i=0;

    int k=0;

    int sum=0;

    int j=-1;


    int lindex=0;

    int subwater=0;

    int sub=0;

    int lastHeight=0;

    int minIndex=0;

    int trapIndex=0;

    int maxHeight=0;


    int tmpt=0;

    Index *indexarr=NULL;

    void quikSort(Index *arr,int l,int r);


    if(heightSize<=0)
    {
        return 0;
    }
    indexarr=(Index *)malloc(sizeof(Index)*heightSize);

 

    for(i=0;i<heightSize;i++)
    {
        (indexarr+i)->val=height[i];
        (indexarr+i)->index=i;
    }

    quikSort(indexarr,0,heightSize-1);

    maxHeight=indexarr[heightSize-1].val;

    sum=maxHeight*heightSize;


  /**
 * 减去左边不能节水的面积
 */
   for(i=0;i<heightSize;i++)
   {
       if(height[i]<=0)
       {
           continue;
       }

    

      if(height[i]>lastHeight)
      {
          sub+=(height[i]-lastHeight)*i;
          lastHeight=height[i];
      }

      if(height[i]>=maxHeight)
      {
          break;
      }
   
   }


  /**
 *减去右边不能节水的面积
 */
    lastHeight=0;
   for(i=heightSize-1;i>=0;i--)
   {
       if(height[i]<=0)
       {
           continue;
       }

      
      if(height[i]>lastHeight)
      {
          sub+=(height[i]-lastHeight)*(heightSize-1-i);
          lastHeight=height[i];
      }

        if(height[i]>=maxHeight)
      {
          break;
      }

   }


   /**
 *
 * 减去柱子占用的面积
 */
   for(i=0;i<heightSize;i++)
   {
       sub+=height[i];
   }

	/**
 * 总面积减去不能接水的面积就是能接水的面积
 */
   return sum-sub;
   
}

/**
 * 此解法在height很大的时候是很慢的
 *
 * 思路很简单，一级一级的求解能接到水的数量，然后把一级一级的加起来
 *
 * 首先找到最小的min
 *
 * 然后遍历找到一个比min大于等于的，如果第一次遇到就标记，如果是第二次遇到就计算两次索引之间的差*min就是水量
 *
 * 遍历结束了，把所有的高度都减去min，开始算下一层的水量
 *
 * 只到高度为0了
 */
int trap(int* height, int heightSize){


    int i=0;

    int k=0;

    int sum=0;

    int j=-1;

    int g1=0;

 

    Index *indexarr=(Index *)malloc(sizeof(Index)*heightSize);
	
    void quikSort(Index *arr,int l,int r);

    for(i=0;i<heightSize;i++)
    {
        (indexarr+i)->val=height[i];
        (indexarr+i)->index=i;
    }

    quikSort(indexarr,0,heightSize-1);


    int min=-1;

    do{

    
    do
    {
        min=height[indexarr[k++].index];
	
        if(k>=heightSize)
        {
            return sum;
        }

    }while(min<=0);
  

    for(i=0;i<heightSize;i++)
    {
  
       if(height[i]>=min)
       {

          
           
              if(j<0)
              {
                    for(;i<heightSize;i++)
                    {
                        if(height[i]<=0)
                        {
                            break;
                        }
                    
                    }

                j=i;
            


              }
              else
              {
             
                sum+=(i-j)*min;
                j=-1;

               
                i--;
              }

         


       }
        
    }

    g1=0;
    j=-1;
    
    for(i=0;i<heightSize;i++)
    {
       
	height[i]-=min;
        if(height[i]>=1)
        {
            g1=1;
        }
    }

    }while(g1);

    return sum;
}


/**
 *使用排序是为了方便找到最小的min
 */
void quikSort(Index *arr,int l,int r)
{
	
	if(r<=l)
	{
	
		return;
	}



	int i=l,j=r,t;


	int ele=arr[r].val;

	while(i<j)
	{
	

		for(;i<j;i++)
	        {
			if(arr[i].val>ele)
			{
				break;
			}
		}



		for(;j>i;j--)
		{
			if(arr[j].val<=ele)
			{
				break;
			}
		
		}




		if(i>=j)
		{
			break;
		}



		t=arr[i].val;
		arr[i].val=arr[j].val;
		arr[j].val=t;

        t=arr[i].index;
        arr[i].index=arr[j].index;
        arr[j].index=t;

	}


	quikSort(arr,l,i-1);
	quikSort(arr,i,r);


}

int main(int argc,char **argv)
{




	int i;

	Index *arr=(Index *)malloc(sizeof(Index)*(argc-1));

	int *traparr=(int *)malloc(sizeof(int)*(argc-1));

	void  quikSort(Index *,int ,int );

	for(i=1;i<argc;i++)
	{
		arr[i-1].val=atoi(*(argv+i));
		arr[i-1].index=i-1;
		printf("%d\t",arr[i-1]);

		traparr[i-1]=arr[i-1].val;

	
	}

	printf("\n");
	
	

	printf("trap result is :\t%d\n",trap(traparr,argc-1));		
	quikSort(arr,0,argc-2);

	for(i=0;i<argc-1;i++)
        {
                printf("%d:%d\t",arr[i].index,arr[i].val);

        }

	return 0;
}
